#pragma once

#include <iostream>
#include <vector>

using namespace std;

class UnionFindSet
{
private:
    vector<int> _a;
public:
    UnionFindSet(int n = 256) : _a(n, -1) {}

    void Union(int x, int y)
    {
        int RootX = FindRoot(x);
        int RootY = FindRoot(y);
        if (RootX == RootY) return;
        _a[RootX] += _a[RootY];
        _a[RootY] = RootX;
    }

    int FindRoot(size_t x)
    {
        if (x >= _a.size())
        {
            _a.resize(max(x + 1, _a.size()*2), -1);
            return x;
        }
        int root = x;
        while (_a[root] >= 0)  
        {
            root = _a[root];
        }

        while (_a[x] >= 0)
        {
            int parent = _a[x];
            _a[x] = root;
            x = parent;
        }
        return root;
    }

    int SetSize()
    {
        int ret = 0;
        for (auto& x : _a) ret += (x < 0);
        return ret;
    }

    bool IsUnion(int x, int y)
    {
        return FindRoot(x) == FindRoot(y);
    }
};